package linearList;

public class LinkedList<T> implements ILinkedList<T> {
    public Node<T> head;

    public LinkedList() {
        this.head = new Node<>();
    }

    public LinkedList(T[] values) {
        this();
        Node<T> p = this.head;
        for (T data : values) {
            p.next = new Node<T>(data, null);
            p = p.next;
        }
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == null;
    }

    @Override
    public int size() {
        int count = 0;
        for (Node<T> p = this.head.next; p != null; p = p.next) {
            count++;
        }
        return count;
    }

    /**
     * 获取索引i节点，超出范围返回null
     * @param i 索引，从0开始
     * @return
     */
    private Node<T> getNode(int i) {
        // 参数校验
        if (i < 0) {
            System.out.println("invalid param i of get(i)");
            return null;
        }

        Node<T> p = this.head;
        for (int j = 0; j <= i; j++) {
            if (p.next == null) {
                System.out.println("invalid index in getNode(i)");
                return null;
            } else {
                p = p.next;
            }
        }
        return p;
    }

    @Override
    public T get(int i) {
        Node<T> node = this.getNode(i);
        return node == null ? null : node.data;
    }

    @Override
    public void set(int i, T x) {
        Node<T> node = this.getNode(i);
        if (node != null) {
            node.data = x;
        }
    }

    @Override
    public Node<T> insert(int i, T x) {
        // 参数校验
        if (x == null) {
            System.out.println("invalid param x in set(i,x): null");
            return null;
        }
        if (i < 0) {
            System.out.println("invalid param i in set(i,x): i < 0 ");
            return null;
        }

        // front指向要插入的节点之前，即 i-1 位置
        Node<T> front = head;
        if (i > 0) {
            front = getNode(i - 1);
        }

        if (front == null) {
            return null;
        } else {
            front.next = new Node<T>(x, front.next);
            return front.next;
        }
    }

    @Override
    public Node<T> insert(T x) {
        return insert(this.size(), x);
    }

    @Override
    public T remove(int i) {
        if (i < 0) {
            System.out.println("invalid param i in set(i,x): i < 0 ");
            return null;
        }

        // front指向要插入的节点之前，即 i-1 位置
        Node<T> front = head;
        if (i > 0) {
            front = getNode(i - 1);
        }

        if (front == null || front.next == null) {
            return null;
        } else {
            Node<T> delNode = front.next;
            front.next = front.next.next;
            return delNode.data;
        }
    }

    @Override
    public void clear() {
        this.head.next = null;
    }

    @Override
    public Node<T> search(T key) {
        for (Node<T> p = this.head.next; p != null; p = p.next) {
            if (key.equals(p.data))
                return p;
        }
        return null;
    }

    @Override
    public T removeByKey(T key) {
        Node<T> front = this.head;      // 指向前一个节点
        Node<T> p = front.next;         // 指向当前节点
        while(p != null) {
            if (key.equals(p.data)) {
                front.next = p.next;
                return p.data;
            } else {
                front = p;
                p = p.next;
            }
        }
        return null;
    }

    public void reverse() {
        Node<T> p = this.head.next, succ = null, front = null;

        while (p != null) {
            succ = p.next;               //设置succ是p结点的后继结点
            p.next = front;                //使p.next指向p结点的前驱结点
            front = p;
            p = succ;
        }
        this.head.next = front;
    }


    public String toString() {
        String s = "linked list: (";
        for (Node<T> p = this.head.next; p != null; p = p.next) {
            s = s + p.data.toString();
            if (p.next != null) {
                s = s + ", ";
            }
        }
        s = s + ")";

        return s;
    }

    public static void main(String[] args) {
        System.out.println("--测试初始化--");
        Integer[] data = {66, 33, 15, 11, 78, 4, 6, 9, 6, 10};
        LinkedList<Integer> linkedList = new LinkedList<Integer>(data);
        System.out.println(linkedList);

        System.out.println("--测试getNode 5, 0, 100--");
        Node<Integer> node5 = linkedList.getNode(5);
        System.out.println(node5);
        Node<Integer> node0 = linkedList.getNode(0);
        System.out.println(node0);
        Node<Integer> node100 = linkedList.getNode(100);
        System.out.println(node100);

        System.out.println("--测试insert(2, 22)--");
        linkedList.insert(2, 22);
        System.out.println(linkedList);

        System.out.println("--测试insert 10个元素--");
        for (int i = 20; i <= 30; i++) {
            linkedList.insert(i);
        }
        System.out.println(linkedList);

        System.out.println("--测试remove index为5的元素--");
        linkedList.remove(5);
        System.out.println(linkedList);

        System.out.println("--测试获取 index为5的元素--");
        System.out.println(linkedList.get(5));

        System.out.println("--测试设置 index为5的元素为100--");
        linkedList.set(5, 100);
        System.out.println(linkedList);

        System.out.println("--测试查找元素等于100--");
        System.out.println(linkedList.search(100));

        System.out.println("--测试remove by key--");
        linkedList.removeByKey(new Integer(100));
        System.out.println(linkedList);

        System.out.println("--测试reverse--");
        linkedList.reverse();
        System.out.println(linkedList);

    }
}
